//
//  Problem78.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 78. 子集
 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 示例 1：
     输入：nums = [1,2,3]
     输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 示例 2：
     输入：nums = [0]
     输出：[[],[0]]
 提示：
     1 <= nums.length <= 10
     -10 <= nums[i] <= 10
     nums 中的所有元素 互不相同
 */
@objcMembers class Problem78: NSObject {
    func solution() {
        print(subsetsS([1,2,3]))
        print(subsetsS([0]))
    }
    /*
     二进制+位运算
     数组中每一个数字有2个选择：在子集中， 不在子集中
     000        []
     001        [3]
     010        [2]
     100        [1]
     011        [2, 3]
     */
    func subsets(_ nums: [Int]) -> [[Int]] {
        let n = 1 << nums.count
        var result:[[Int]] = []
        for i in 0..<n {
            var list: [Int] = []
            for wi in 0..<nums.count {
                if i & 1 << wi != 0 {
                    list.append(nums[wi])
                }
            }
            result.append(list)
        }
        return result
    }
    
    /*
     遍历数组nums，每次讲数组放入到已存在的数组中
     例如：初始值是：[]
     遍历: 1  [] [1]
     遍历: 2  [] [1] 给[]添加2 -> [2], 给[1]添加2 -> [1,2]
              [] [1] [2] [1,2]
     */
    func subsetsS(_ nums: [Int]) -> [[Int]] {
        var result:[[Int]] = [[]]
        for n in nums {
            var tResult:[[Int]] = []
            for list in result {
                var tList = list
                tList.append(n)
                
                tResult.append(tList)
            }
            result.append(contentsOf: tResult)
        }
        return result
    }
}
